// date:20-07-11
// The program addresses the problem of how must a 
// certain amount of money be divided into a set of denominations,
// so that the number of coins is minimum.A recursive solution is used with 
// memoization. 

/* The function getMinAndDenom returns the minimum number of 
 * coins required and how much of each denomination is required
 * denom: an array containing the available denominations  
 * sum:the amount of money to be formed using the coins. 
 * */ 
def getMinAndDenom(denom:Array[Int],sum:Int):(Int,Array[Int])= {
    if(denom==null) error("null denom passed")
    // memoMin contains the minimum number of coins required with denomination   
    // 0 to sum
    var memoMin=new Array[Int](sum+1)
    // memoDen will keep track of the amount of each denomination required to 
    // produce 0 to sum 
    var memoDen=new Array[Array[Int]](sum+1)
    
    // initialize the memoized arrays
    for(d <- denom) {
        memoMin(d)=1
        memoDen(d)=new Array[Int](denom.length)
        memoDen(d)(find(d,denom))=1
    }
    
   //find returns the position of an element a in an array b
   def find(a:Int,b:Array[Int]):Int= {
       for(i <- 0 until b.length) {
           if(b(i)==a) return i
       }
       return -1
   }
   // addArrays returns the sum of two integer arrays xs and ys that are assumed 
   // to be of the same length
   def addArrays(xs:Array[Int],ys:Array[Int]):Array[Int]= {
       var zs=new Array[Int](xs.length)
       for(i <- 0 until zs.length) {zs(i)=xs(i) + ys(i)}
       zs
   } 
   // getMin1 is a recursive function It uses the outerdefined memoDen and 
   // memoMin to store its values.Also,this function makes up the core of the 
   // program and the function getMinAndDenom 
   def getMin1(sum:Int):(Int,Array[Int])= {
        if(sum<=0) return (-1,null)
        else 
            if(memoMin(sum)!=0) {
               return (memoMin(sum),memoDen(sum))
             } 
            else {
                // BestSoFar is the minimum coins required to produce the 
                // respective sum. 
                var BestSoFar=Int.MaxValue
                // BestArray is an array that updates the best combination of 
                // coins required.
                var BestArray:Array[Int]=null
                for(d <-denom) {
                    var thisOne=getMin1(sum-d)
                    var thisTwo=getMin1(d)
                    if(thisOne._1!=(-1) && // no sum found
                       thisTwo._1!=(-1) && // no sum found
                       thisOne._1 + thisTwo._1 < BestSoFar) {
                        BestSoFar=thisOne._1 + thisTwo._1
                        BestArray=addArrays(thisOne._2,thisTwo._2)
                    }
                }
                if(BestSoFar==Int.MaxValue) BestSoFar= (-1)  
                
                // update the memoized arrays
                memoMin(sum)=BestSoFar
                memoDen(sum)=BestArray
                return (BestSoFar,BestArray)
            }
        }
    // call the inner function    
    getMin1(sum)
}

test("this is the required number of coins") {    
    getMinAndDenom(new Array[Int](0),4) should equal((-1,null))
    var a=getMinAndDenom(Array[Int](4),4)
    a._1 should equal (1)
    a._2 should equal (Array(1))
    var b=getMinAndDenom(Array(2,3),50) 
    b._1 should equal (17)
    b._2 should equal (Array(1,16))
    var c= getMinAndDenom(Array(5,4,1),12) 
    c._1 should equal (3)
    c._2 should equal (Array(0,3,0))
}
